package hero.mps.leet_code_17;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LetterCombinationsOfIphoneNumber {
    public static List<String> letterCombinations(String digits) {
        LinkedList<String> combinations = new LinkedList<>();
        // 如果输入的数字字符串为空，则直接返回空组合列表
        if (digits == null || digits.length() == 0) return combinations;
        // 映射关系数组，将数字映射到对应的字母集合
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        // 初始化组合列表，加入一个空字符串
        combinations.add("");
        // 遍历输入的数字字符串
        for (int i = 0; i < digits.length(); i++) {
            // 获取当前字符对应的数字
            int digit = Character.getNumericValue(digits.charAt(i));
            // 当组合列表中的字符串长度等于当前遍历到的位置时
            while (combinations.peek().length() == i) {
                // 取出组合列表中的字符串
                String t = combinations.remove();
                // 遍历当前数字对应的字母集合
                for (char s : mapping[digit].toCharArray()) {
                    // 将当前字母添加到取出的字符串后面，并将新字符串加入组合列表
                    combinations.add(t + s);
                }
            }
        }
        // 返回最终的组合列表
        return combinations;
    }

    public static List<String> letterCombinations1(String digits) {
        LinkedList<StringBuilder> combinations = new LinkedList<>();
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        // 初始化一个空的StringBuilder对象并添加到combinations列表中
        combinations.add(new StringBuilder());

        for (int i = 0; i < digits.length(); i++) {
            int digit = Character.getNumericValue(digits.charAt(i));

            // 当combinations列表中第一个StringBuilder对象的长度等于当前遍历的索引时，执行循环
            while (combinations.peek().length() == i) {
                // 从combinations列表中移除第一个StringBuilder对象
                StringBuilder prefix = combinations.remove();

                // 遍历当前数字对应的字符数组
                for (char letter : mapping[digit].toCharArray()) {
                    // 创建一个新的StringBuilder对象，并将prefix对象和当前字符添加到其中
                    // 然后将新的StringBuilder对象添加到combinations列表中
                    combinations.add(new StringBuilder(prefix).append(letter));
                }
            }
        }

        // 创建一个新的ArrayList对象result
        ArrayList<String> result = new ArrayList<>();

        // 遍历combinations列表中的每个StringBuilder对象
        for (StringBuilder combination : combinations) {
            // 将每个StringBuilder对象转换为字符串，并添加到result列表中
            result.add(combination.toString());
        }

        // 返回result列表
        return result;
    }
    String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    ArrayList<String> result = new ArrayList<>();
    public List<String> letterCombinations2(String digits) {
        if (digits == null || digits.length() == 0) return result;
        backTack(digits, 0, new StringBuilder());
        return result;
    }
    public void backTack(String digits, int index, StringBuilder sb) {
        // 如果已经遍历完digits字符串的所有字符
        if (index == digits.length()) {
            // 将当前构建的字符串添加到结果列表中
            result.add(sb.toString());
            return;
        }
        // 获取当前遍历到的字符
        char digit = digits.charAt(index);
        // 根据当前字符获取对应的字母集合
        String letters = mapping[digit - '0'];
        // 遍历字母集合中的每个字母
        for (char letter : letters.toCharArray()) {
            // 将当前字母添加到构建字符串的末尾
            sb.append(letter);
            // 递归调用backTack方法，继续处理下一个字符
            backTack(digits, index + 1, sb);
            // 回溯，删除构建字符串末尾的字母
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {

        System.out.println(new LetterCombinationsOfIphoneNumber().letterCombinations2("23"));
    }
}
